package com.company.剑指offer每日刷题.普通版;

import java.util.Stack;

/**
 * 剑指 Offer 30. 包含min函数的栈
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * 示例:
 *
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.min();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.min();   --> 返回 -2.
 *
 *
 * 提示：
 * 各函数的调用总次数不超过 20000 次
 * */
public class MinStack {
    /**
     * 方法：辅助栈法
     * 思路：
     *      1.定义两个栈，a,b,a为主栈，用来存储所有元素，负责入栈和出栈；b为辅助栈，用来存储入栈时的非升序元素的
     *      2.入栈的元素e必入a栈，而如果e小于等于了b栈的栈顶元素，才入b栈。
     * 思考：为什么最小值是始终出现在辅助栈b的顶部元素呢？
     *      因为，元素e要进栈辅助栈b的原则是，e小于等于b栈顶元素。可以理解成b栈式用来存储，目前为止所有入栈元素中更小的元素的。
     * */
    private Stack<Integer> a;
    private Stack<Integer> b;
    public MinStack() {
        a = new Stack<>();
        b = new Stack<>();
    }

    public void push(int x) {
        a.push(x);
        if(b.empty() || b.peek() >= x){
            b.push(x);
        }
    }

    public void pop() {
        if(a.pop().equals(b.peek())){
            b.pop();
        }
    }

    public int top() {
        return a.peek();
    }

    public int min() {
        return b.peek();
    }
}
